#include <iostream>
#include <cmath>
#include <cassert>
#include <ctime>
#include "utils.h"

using namespace std;

// 如何写出正确的程序。其实就是要保证边界的正确
template <typename T>
int binarySearch(T arr[], int n, T target)
{
    int l = 0, r = n - 1; // 在[l...r]的范围内寻找target
    // 我们定义清楚l和r的含义，下面就是要在循环中也维护这个含义
    // 专业的术语叫做“循环不变量”，本例中，就是target在[l...r]这个闭区间内
    // 当我们对l和r的含义做出改变后，看下程序该怎么写，参见solution2.cpp

    // 当l==r时，区间[l...r]依然是有效的
    while (l <= r)
    {
        // 整型溢出，C++不报错，所以当l和r足够大时，可能溢出
        // 所以这个问题在62年才被改正（1946年就提出了二分查找法）
        // int mid = (l + r) / 2;
        int mid = l + (r - l) / 2; // 不用加法

        if (target == arr[mid])
            return mid;

        if (target > arr[mid])
            l = mid + 1; // target在[mid+1...r]中
        else             // target<arr[mid]
            r = mid - 1; // target在[l...mid-1]中
    }

    return -1;
}

int main()
{
    int n = 1000000;
    int *data = MyUtil::generateOrderedArray(n);

    clock_t startTime = clock();
    for (int i = 0; i < n; i++)
        assert(i == binarySearch(data, n, i));
    clock_t endTime = clock();

    cout << "Binary Search test complete." << endl;
    cout << "Time cost: " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;

    return 0;
}